//
// Description: STL之nth_element()使用
// Created by Loading on 2021/1/24.
//

#include <bits/stdc++.h>

using namespace std;

int main() {
    int k = 3;
    //不重复数组
    vector<int> v1 = {4, 6, 2, 3, 1, 8, 9, 7, 5};
    int n1 = v1.size();
    //存在重复数组
    vector<int> v2 = {4, 4, 4, 9, 4, 8, 4, 3, 5, 9};
    int n2 = v2.size();

    //将数组中的k-1位置（下标从0开始）进行放置，可求第k小的数（不重复情况下）
    nth_element(v1.begin(), v1.begin() + k - 1, v1.end());
    for (auto x : v1) {
        cout << x << " ";
    }
    cout << endl;
    cout << "第" << k << "小的数为：" << v1[k - 1] << endl;

    //若要求第k大的数（不重复情况下），则转换为求第n1 - k + 1小的数，放置n1 - k位置（下标从0开始）
    nth_element(v1.begin(), v1.begin() + n1 - k, v1.end());
    for (auto x : v1) {
        cout << x << " ";
    }
    cout << endl;
    cout << "第" << k << "大的数为：" << v1[n1 - k] << endl;

    ///存在重复的数组，只放置对应位置，不能保证第k小或第k大
    nth_element(v2.begin(), v2.begin() + k - 1, v2.end());
    for (auto x : v2) {
        cout << x << " ";
    }
    cout << endl;

    nth_element(v2.begin(), v2.begin() + n2 - k, v2.end());
    for (auto x : v2) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}